[题解]LG2466 Sue的小球

2020-11-01

https://www.luogu.com.cn/problem/P2466

LG2466 Sue的小球

这个区间 DP 比较显。

$f(l,r,0/1)$ 代表捡完 $[l,r]$ 且最后在 $l/r$ 的最小损耗。

$f(l,r,0)=\min \{f(l+1,r,0)+(x_{l+1}-x_{l})\times (sum-sum_{l+1,r}), f(l+1,r,1)+(x_r-x_l)\times (sum-sum_{l+1,r})\}$

$f(l,r,1)=\min \{f(1,r-1,1)+(x_{r}-x_{r-1})\times (sum-sum_{l,r-1}), f(l,r-1,0)+(x_r-x_l)\times (sum-sum_{l,r-1})\}$

然后初始状态为 sue 所在的点也看成一个空的球，然后初始化为 $0$ 。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=1009;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,x0,f[N][N][2],s[N];
struct ball {int x,y,v;}a[N];
bool cmp(const ball &a,const ball &b) {return a.x<b.x;}

int dp(int l,int r) {
	if(f[l][r][0]!=0x3f3f3f3f3f3f3f3f||l==r) return min(f[l][r][0],f[l][r][1]);
	dp(l+1,r), dp(l,r-1);
	f[l][r][0]=min(f[l+1][r][0]+(a[l+1].x-a[l].x)*(s[n]-s[r]+s[l]),f[l+1][r][1]+(a[r].x-a[l].x)*(s[n]-s[r]+s[l]));
	f[l][r][1]=min(f[l][r-1][1]+(a[r].x-a[r-1].x)*(s[n]-s[r-1]+s[l-1]),f[l][r-1][0]+(a[r].x-a[l].x)*(s[n]-s[r-1]+s[l-1]));
	return min(f[l][r][0],f[l][r][1]);
}

signed main() {
	n=read(), x0=read();
	rep(i,1,n) a[i].x=read();
	rep(i,1,n) a[i].y=read();
	rep(i,1,n) a[i].v=read();
	a[++n]=(ball){x0,0,0};
	sort(a+1,a+n+1,cmp);
	memset(f,0x3f,sizeof(f));
	rep(i,1,n) if(a[i].x==x0&&!a[i].y&&!a[i].v) f[i][i][0]=f[i][i][1]=0;
	rep(i,1,n) s[i]=s[i-1]+a[i].v;
	int ans=0;
	rep(i,1,n) ans+=a[i].y;
	printf("%.3lf",1.*(ans-dp(1,n))/1000);
	return 0;
}